【题解】 luogu P1025 数的划分

小蒟蒻好久没有写一篇搜索的题解了（明明可以DP的说，今天用DFS解决一下这道题目

观察题意，我们可以发现题目中所求的组合总数的序列是一个单调不下降的序列，那么我们在DFS时设置参数就可以设置三个，分别是K1（保存还能用的数的个数），sum（当前记录的使用的数的和），num（当前序列选的数）

在这里多讲一下num这个参数，因为选的数的序列是单调不下降的，所以我们选的数一定比前面大或者相同，因此我们可以用num保存当前选的数，这样就可以保证序列不会重，并且这也是个简单的优化。（虽然不如DP快，但是好想啊qwq，并且亲测DP空间比DFS要大一点（虽然时间快了N倍QAQ））

上代码（代码中也有部分解释

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int ans=0,n,k;

void dfs(int num,int sum,int k1)
{
	if(k1==0)
	{
		if(sum==n)
		{
 			ans++;
			return;
		}
		else return;
	}
	for(int i=num; sum+i<=n; i++)//sum+i<=n是一个很简单的优化，防止溢出并减少循环次数（其实还有更好地优化就是其他大佬题解里的%%%）
		dfs(i,sum+i,k1-1);//（dfs深度优先一层层向下搜索就行了）
}

int main()
{
	scanf("%d%d",&n,&k);
	if(k==1){ printf("1"); return 0; }//有一点小懒qwq，其实不用，因为n很小
	dfs(1,0,k);
	printf("%d",ans);//输出方案总数
}